{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Two Sum"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #hash-table"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #哈希表"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: twoSum"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #两数之和"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一个整数数组 <code>nums</code>&nbsp;和一个整数目标值 <code>target</code>，请你在该数组中找出 <strong>和为目标值 </strong><em><code>target</code></em>&nbsp; 的那&nbsp;<strong>两个</strong>&nbsp;整数，并返回它们的数组下标。</p>\n",
    "\n",
    "<p>你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。</p>\n",
    "\n",
    "<p>你可以按任意顺序返回答案。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong class=\"example\">示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [2,7,11,15], target = 9\n",
    "<strong>输出：</strong>[0,1]\n",
    "<strong>解释：</strong>因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。\n",
    "</pre>\n",
    "\n",
    "<p><strong class=\"example\">示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [3,2,4], target = 6\n",
    "<strong>输出：</strong>[1,2]\n",
    "</pre>\n",
    "\n",
    "<p><strong class=\"example\">示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [3,3], target = 6\n",
    "<strong>输出：</strong>[0,1]\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>2 &lt;= nums.length &lt;= 10<sup>4</sup></code></li>\n",
    "\t<li><code>-10<sup>9</sup> &lt;= nums[i] &lt;= 10<sup>9</sup></code></li>\n",
    "\t<li><code>-10<sup>9</sup> &lt;= target &lt;= 10<sup>9</sup></code></li>\n",
    "\t<li><strong>只会存在一个有效答案</strong></li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>进阶：</strong>你可以想出一个时间复杂度小于 <code>O(n<sup>2</sup>)</code> 的算法吗？</p>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [two-sum](https://leetcode.cn/problems/two-sum/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [two-sum](https://leetcode.cn/problems/two-sum/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[2,7,11,15]\\n9', '[3,2,4]\\n6', '[3,3]\\n6']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoSum(self, nums: List[int], target: int) -> List[int]:\n",
    "        for i in range(len(nums)):\n",
    "            b = []  \n",
    "            for j in range(i+1, len(nums)):\n",
    "                a = nums[i] + nums[j]\n",
    "                if a == target:  \n",
    "                    b.append(i)\n",
    "                    b.append(j)\n",
    "                    return b\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoSum(self, nums, target):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :type target: int\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "        l = len(nums)\n",
    "        for i in range(l):\n",
    "            tmp = target - nums[i]\n",
    "            for j in range(i + 1, l):\n",
    "                if nums[j] == tmp:\n",
    "                    res = [i, j]\n",
    "                    return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoSum(self, nums, target):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :type target: int\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "        for i in range(len(nums)):\n",
    "            for j in range(i+1, len(nums)):\n",
    "                if nums[i] + nums[j] == target:\n",
    "                    return [i, j]\n",
    "        return None\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def twoSum(self, nums, target):\r\n",
    "        \"\"\"\r\n",
    "        :type nums: List[int]\r\n",
    "        :type target: int\r\n",
    "        :rtype: List[int]\r\n",
    "        \"\"\"\r\n",
    "        for i,num in enumerate(nums):\r\n",
    "            if target - num in nums:\r\n",
    "                j = nums.index(target - num)\r\n",
    "                if i != j:\r\n",
    "                    return [i,j]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoSum(self, nums, target):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :type target: int\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "        seen = {}\n",
    "        for i, n in enumerate(nums):\n",
    "            if target - n in seen:\n",
    "                return [seen[target - n], i]\n",
    "            seen[n] = i\n",
    "        return [-1, -1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoSum(self, nums, target):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :type target: int\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "        for i in list(range(len(nums)-1,-1,-1)):\n",
    "            temp=target-nums[i]\n",
    "            for j in list(range(0,i)):\n",
    "                if nums[j]==temp:\n",
    "                    return [j,i]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoSum(self, nums, target):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :type target: int\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "        if len(nums) <= 1:\n",
    "            return False\n",
    "        buff_dict = {}\n",
    "        for i in range(len(nums)):\n",
    "            if nums[i] in buff_dict:\n",
    "                return [buff_dict[nums[i]], i]\n",
    "            else:\n",
    "                buff_dict[target - nums[i]] = i\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoSum(self, nums, target):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :type target: int\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "        map={} \n",
    "        for i,num in enumerate(nums):\n",
    "            if target-num in map:\n",
    "                return map[target-num],i\n",
    "            else:\n",
    "                map[num]=i\n",
    "        print(map)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoSum(self, nums, target):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :type target: int\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "        if target >= 0:\n",
    "            smaller = [[elem, idx] \n",
    "                        for idx, elem in enumerate(nums)\n",
    "                        if elem <= target]\n",
    "            bigger = [[elem, idx] \n",
    "                        for idx, elem in enumerate(nums)\n",
    "                        if elem > target]\n",
    "\n",
    "            for i in range(len(smaller)):\n",
    "                if smaller[i][0] >= 0:\n",
    "                    for j in range(i+1, len(smaller)):\n",
    "                        if (smaller[i][0] + smaller[j][0]) == target:\n",
    "                            return [smaller[i][1], smaller[j][1]]\n",
    "                else:\n",
    "                    for j in range(len(bigger)):\n",
    "                        if (smaller[i][0] + bigger[j][0]) == target:\n",
    "                            return [smaller[i][1], bigger[j][1]]\n",
    "        else:\n",
    "            smaller = [[elem, idx] \n",
    "                        for idx, elem in enumerate(nums)\n",
    "                        if elem <= target]\n",
    "            middle = [[elem, idx] \n",
    "                        for idx, elem in enumerate(nums)\n",
    "                        if elem > target and elem < 0]\n",
    "            bigger = [[elem, idx] \n",
    "                        for idx, elem in enumerate(nums)\n",
    "                        if elem >= 0]\n",
    "\n",
    "            for i in range(len(smaller)):\n",
    "                for j in range(len(bigger)):\n",
    "                    if (smaller[i][0] + bigger[j][0]) == target:\n",
    "                        return [smaller[i][1], bigger[j][1]]\n",
    "            for i in range(len(middle)):\n",
    "                for j in range(i+1, len(middle)):\n",
    "                    if (middle[i][0] + middle[j][0]) == target:\n",
    "                        return [middle[i][1], middle[j][1]]\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoSum(self, nums: List[int], target: int) -> List[int]:\n",
    "        # 解法一\n",
    "        # for i in range(len(nums)):\n",
    "        #     for j in range(i + 1, len(nums)):\n",
    "        #         if nums[i] + nums[j] == target:\n",
    "        #             return [i, j]\n",
    "        # else:\n",
    "        #     return 'no answer'\n",
    "        \n",
    "        \n",
    "        # 解法二\n",
    "        n = len(nums)\n",
    "        d = {}\n",
    "        for i in range(n):\n",
    "            sub = target - nums[i]\n",
    "            if nums[i] in d.keys():\n",
    "                return [d[nums[i]], i]\n",
    "            else:\n",
    "                d[sub] = i"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoSum(self, nums: List[int], target: int) -> List[int]:\n",
    "        l = sorted(enumerate(nums), key=lambda i:i[1])\n",
    "        i = 0\n",
    "        j = len(nums) - 1\n",
    "        while i < j:\n",
    "            if l[i][1] + l[j][1] == target:\n",
    "                return [l[i][0], l[j][0]]\n",
    "            elif l[i][1] + l[j][1] > target:\n",
    "                j -= 1\n",
    "            elif l[i][1] + l[j][1] < target:\n",
    "                i += 1\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoSum(self, nums, target):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :type target: int\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "        \n",
    "        elem = {}\n",
    "        for idx, val in enumerate(nums):\n",
    "            elem[val] = idx\n",
    "            \n",
    "        result = []\n",
    "        for idx in range(len(nums)):\n",
    "            diff  = target - nums[idx]\n",
    "            if diff in elem and elem[diff] != idx:\n",
    "                result.append(idx)\n",
    "                result.append(elem[diff])\n",
    "                break\n",
    "       \n",
    "        return result\n",
    "\n",
    "    def testSolution():\n",
    "        testSolution = Solution()\n",
    "        testArr = [2, 7, 11, 15]\n",
    "        testTarget = 9\n",
    "        \n",
    "        assert testSolution.twoSum(testArr, testTarget) == [0, 1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoSum(self, nums, target):\n",
    "        dict_nums = dict(zip(range(len(nums)),nums))\n",
    "        new_dict = {v: k for k, v in dict_nums.items()}\n",
    "        for i in range(0,len(nums)):\n",
    "            if target-nums[i] in nums:\n",
    "                if i!=new_dict[target-nums[i]]:   # 不可自己加自己  .index() 时间复杂度为O(n)\n",
    "                    return [i,new_dict[target-nums[i]]]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoSum(self, nums, target):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :type target: int\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "        d = {}\n",
    "        for i, v in enumerate(nums):\n",
    "            n = target - v\n",
    "            d[n] = i\n",
    "        for i, n in enumerate(nums):\n",
    "            if n in d.keys() and d.get(n) != i:\n",
    "                return [i,d.get(n)]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoSum(self, nums: 'List[int]', target: 'int') -> 'List[int]':\n",
    "        # {leave:[]}\n",
    "        leaves_dict = {}\n",
    "        \n",
    "        for i,num in enumerate(nums):\n",
    "            leave = target - num\n",
    "            if leave in leaves_dict:\n",
    "                leaves_dict[leave].append(i)\n",
    "            else:\n",
    "                leaves_dict[leave] = [i]\n",
    "        \n",
    "        for i,num in enumerate(nums):\n",
    "            if num in leaves_dict:\n",
    "                indexs = leaves_dict[num]\n",
    "                if len(leaves_dict[num]) > 0 and num*2 != target:\n",
    "                    return  i,indexs[0]\n",
    "                if len(indexs) >= 2 and num*2 == target: \n",
    "                     return  indexs[0],indexs[1]\n",
    "                    \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoSum(self, nums: List[int], target: int) -> List[int]:\n",
    "        dict0 = {}\n",
    "        dict1 = {}\n",
    "        for i in range(len(nums)):\n",
    "            dict0[i] = nums[i]\n",
    "            dict1[nums[i]] = i\n",
    "        for i in range(len(nums)):\n",
    "            n = target - nums[i]\n",
    "            if (n in dict0.values()) & (n in dict1.keys()):\n",
    "                if (dict1[n] != i):\n",
    "                    return [i, dict1[n]]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoSum(self, nums, target):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :type target: int\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "        tar = []\n",
    "        for i in range(len(nums)):\n",
    "            t = target-nums[i]\n",
    "            for j in range(len(tar)):\n",
    "                if nums[i] == tar[j]:\n",
    "                    return [j,i]\n",
    "            tar.append(t)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "#\n",
    "# @lc app=leetcode.cn id=1 lang=python3\n",
    "#\n",
    "# [1] 两数之和\n",
    "#\n",
    "# https://leetcode-cn.com/problems/two-sum/description/\n",
    "#\n",
    "# algorithms\n",
    "# Easy (44.34%)\n",
    "# Total Accepted:    237.2K\n",
    "# Total Submissions: 535K\n",
    "# Testcase Example:  '[2,7,11,15]\\n9'\n",
    "#\n",
    "# 给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。\n",
    "# \n",
    "# 你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。\n",
    "# \n",
    "# 示例:\n",
    "# \n",
    "# 给定 nums = [2, 7, 11, 15], target = 9\n",
    "# \n",
    "# 因为 nums[0] + nums[1] = 2 + 7 = 9\n",
    "# 所以返回 [0, 1]\n",
    "# \n",
    "# \n",
    "#\n",
    "from collections import defaultdict\n",
    "class Solution:\n",
    "    def twoSum(self, nums, target):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :type target: int\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "        d=defaultdict(list)\n",
    "        for i,n in enumerate(nums):\n",
    "            d[n].append(i)\n",
    "        for i,n in enumerate(nums):\n",
    "            index=d[target-n]\n",
    "            if i in index: index.remove(i)\n",
    "            if len(index)>0:\n",
    "                return [i,index[0]]\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoSum(self, nums, target):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :type target: int\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "        d = {i:num for i, num in enumerate(nums)}\n",
    "        d2 = {num:i for i, num in enumerate(nums)}\n",
    "        for i in range(len(nums)):\n",
    "            temp = target - d.get(i)\n",
    "            if temp in d.values() and d2.get(temp) != i:\n",
    "                return [i, d2.get(temp)]\n",
    "\n",
    "            \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class LinearMap(object):\n",
    "\n",
    "    def __init__(self):\n",
    "        self.items = []\n",
    "\n",
    "    # 往表中添加元素\n",
    "    def add(self, k, v):\n",
    "        self.items.append((k, v))\n",
    "\n",
    "    # 线性方式查找元素\n",
    "    def get(self, k):\n",
    "        for key, value in self.items:\n",
    "            if key == k:  # 键存在，返回值，否则抛出异常\n",
    "                return value\n",
    "        return None\n",
    "\n",
    "\n",
    "class BetterMap(object):\n",
    "\n",
    "    def __init__(self, num=100):\n",
    "        self.maps = []\n",
    "        for i in range(num):\n",
    "            self.maps.append(LinearMap())\n",
    "\n",
    "    def find_map(self, k):\n",
    "        index = hash(k) % len(self.maps)\n",
    "        return self.maps[index]\n",
    "\n",
    "    def add(self, k, v):\n",
    "        map = self.find_map(k)\n",
    "        map.add(k, v)\n",
    "\n",
    "    def get(self, k):\n",
    "        map = self.find_map(k)\n",
    "        return map.get(k)\n",
    "        \n",
    "class HashMap(object):\n",
    "    def __init__(self):\n",
    "        # 初始化总表为，容量为2的表格（含两个子表）\n",
    "        self.maps = BetterMap(2)\n",
    "        self.num = 0  # 表中数据个数\n",
    "\n",
    "    def get(self, k):\n",
    "        return self.maps.get(k)\n",
    "\n",
    "    def add(self, k, v):\n",
    "        # 若当前元素数量达到临界值（子表总数）时，进行重排操作\n",
    "        # 对总表进行扩张，增加子表的个数为当前元素个数的两倍！\n",
    "        if self.num == len(self.maps.maps):\n",
    "            self.resize()\n",
    "\n",
    "        # 往重排过后的 self.map 添加新的元素\n",
    "        self.maps.add(k, v)\n",
    "        self.num += 1\n",
    "\n",
    "    def resize(self):\n",
    "        # 重排操作，添加新表, 注意重排需要线性的时间\n",
    "        # 先建立一个新的表,子表数 = 2 * 元素个数\n",
    "        new_maps = BetterMap(self.num * 2)\n",
    "\n",
    "        for m in self.maps.maps:  # 检索每个旧的子表\n",
    "            for k, v in m.items:  # 将子表的元素复制到新子表\n",
    "                new_maps.add(k, v)\n",
    "\n",
    "        self.maps = new_maps  # 令当前的表为新表\n",
    "        \n",
    "class Solution:\n",
    "    def twoSum(self, nums, target):\n",
    "        result = []\n",
    "        length = len(nums)\n",
    "        map = HashMap()\n",
    "\n",
    "        for i in range(length):\n",
    "            another = target - nums[i]\n",
    "            second = map.get(another)\n",
    "            if second is not None:\n",
    "                result.append(second)\n",
    "                result.append(i)\n",
    "                return result\n",
    "            else:\n",
    "                map.add(nums[i], i)\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    import collections\n",
    "    def twoSum(self, nums, target):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :type target: int\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "        dic = collections.defaultdict(list)\n",
    "        dic_n = collections.defaultdict(int)\n",
    "        for i in range(len(nums)):\n",
    "            dic[nums[i]].append(i)\n",
    "            dic_n[nums[i]] += 1\n",
    "        se = set(nums)\n",
    "        for i in range(len(nums)):\n",
    "            dic_n[nums[i]] -= 1\n",
    "            if dic_n[nums[i]] == 0:\n",
    "                se.remove(nums[i])\n",
    "            dic[nums[i]].remove(i)\n",
    "            if target - nums[i] in se:\n",
    "                return [i, dic[target-nums[i]][0]]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoSum(self, nums, target):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :type target: int\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "        nums_dict = {}\n",
    "        score = []\n",
    "        for j,k in enumerate(nums):\n",
    "            if k not in nums_dict.keys():\n",
    "                nums_dict[k] = set([j])\n",
    "            else:\n",
    "                nums_dict[k].add(j)\n",
    "        for x in nums_dict:\n",
    "            if target -x in nums_dict.keys():\n",
    "                if (x == target-x)and(len(nums_dict[x])>1):\n",
    "                    score.append(nums_dict[x].pop())\n",
    "                    score.append(nums_dict[x].pop())\n",
    "                    break\n",
    "                elif x!= target-x :\n",
    "                    score.append(nums_dict[x].pop())\n",
    "                    score.append(nums_dict[target-x].pop())\n",
    "                    break\n",
    "        return score       "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoSum(self, nums, target):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :type target: int\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "        numdic = {}\n",
    "        for i,value in enumerate(nums):\n",
    "            if value in numdic.keys():\n",
    "                numdic[value].append([i,False])\n",
    "            else:\n",
    "                numdic[value]=[[i,False]]\n",
    "        sumdic = {}\n",
    "        for i,value in enumerate(nums):\n",
    "            sumdic[value]=target-value\n",
    "            \n",
    "        for i,value in enumerate(nums):\n",
    "            try:\n",
    "                numdic[value][0][1]=True\n",
    "                if numdic[sumdic[value]][0][1]==False:\n",
    "                    return [numdic[value][0][0],numdic[sumdic[value]][0][0]]\n",
    "                else:\n",
    "                    return [numdic[value][0][0],numdic[value][1][0]]\n",
    "            except:\n",
    "                numdic[value][0][1]=False\n",
    "                pass\n",
    "        return []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class LinearMap(object):\n",
    "\n",
    "    def __init__(self):\n",
    "        self.items = []\n",
    "\n",
    "    # 往表中添加元素\n",
    "    def add(self, k, v):\n",
    "        self.items.append((k, v))\n",
    "\n",
    "    # 线性方式查找元素\n",
    "    def get(self, k):\n",
    "        for key, value in self.items:\n",
    "            if key == k:  # 键存在，返回值，否则抛出异常\n",
    "                return value\n",
    "        return None\n",
    "\n",
    "\n",
    "class BetterMap(object):\n",
    "\n",
    "    def __init__(self, num=100):\n",
    "        self.maps = []\n",
    "        for i in range(num):\n",
    "            self.maps.append(LinearMap())\n",
    "\n",
    "    def find_map(self, k):\n",
    "        index = hash(k) % len(self.maps)\n",
    "        return self.maps[index]\n",
    "\n",
    "    def add(self, k, v):\n",
    "        map = self.find_map(k)\n",
    "        map.add(k, v)\n",
    "\n",
    "    def get(self, k):\n",
    "        map = self.find_map(k)\n",
    "        return map.get(k)\n",
    "        \n",
    "class HashMap(object):\n",
    "    def __init__(self):\n",
    "        # 初始化总表为，容量为2的表格（含两个子表）\n",
    "        self.maps = BetterMap(150)\n",
    "        self.num = 0  # 表中数据个数\n",
    "\n",
    "    def get(self, k):\n",
    "        return self.maps.get(k)\n",
    "\n",
    "    def add(self, k, v):\n",
    "        # 若当前元素数量达到临界值（子表总数）时，进行重排操作\n",
    "        # 对总表进行扩张，增加子表的个数为当前元素个数的两倍！\n",
    "        if self.num == len(self.maps.maps):\n",
    "            self.resize()\n",
    "\n",
    "        # 往重排过后的 self.map 添加新的元素\n",
    "        self.maps.add(k, v)\n",
    "        self.num += 1\n",
    "\n",
    "    def resize(self):\n",
    "        # 重排操作，添加新表, 注意重排需要线性的时间\n",
    "        # 先建立一个新的表,子表数 = 2 * 元素个数\n",
    "        new_maps = BetterMap(self.num * 2)\n",
    "\n",
    "        for m in self.maps.maps:  # 检索每个旧的子表\n",
    "            for k, v in m.items:  # 将子表的元素复制到新子表\n",
    "                new_maps.add(k, v)\n",
    "\n",
    "        self.maps = new_maps  # 令当前的表为新表\n",
    "        \n",
    "class Solution:\n",
    "    def twoSum(self, nums, target):\n",
    "        result = []\n",
    "        length = len(nums)\n",
    "        map = HashMap()\n",
    "\n",
    "        for i in range(length):\n",
    "            another = target - nums[i]\n",
    "            second = map.get(another)\n",
    "            if second is not None:\n",
    "                result.append(second)\n",
    "                result.append(i)\n",
    "                return result\n",
    "            else:\n",
    "                map.add(nums[i], i)\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoSum(self,nums,target):\n",
    "        i=len(nums)-1\n",
    "        remain= target-nums[i]\n",
    "        for j in range(len(nums)-1):\n",
    "            if remain==nums[j]:\n",
    "                return [j,i]\n",
    "\n",
    "        del nums[i]\n",
    "        return self.twoSum(nums,target)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "#\n",
    "# @lc app=leetcode id=1 lang=python3\n",
    "#\n",
    "# [1] Two Sum\n",
    "#\n",
    "# https://leetcode.com/problems/two-sum/description/\n",
    "#\n",
    "# algorithms\n",
    "# Easy (40.35%)\n",
    "# Total Accepted:    1.4M\n",
    "# Total Submissions: 3.5M\n",
    "# Testcase Example:  '[2,7,11,15]\\n9'\n",
    "#\n",
    "# Given an array of integers, return indices of the two numbers such that they\n",
    "# add up to a specific target.\n",
    "# \n",
    "# You may assume that each input would have exactly one solution, and you may\n",
    "# not use the same element twice.\n",
    "# \n",
    "# Example:\n",
    "# \n",
    "# \n",
    "# Given nums = [2, 7, 11, 15], target = 9,\n",
    "# \n",
    "# Because nums[0] + nums[1] = 2 + 7 = 9,\n",
    "# return [0, 1].\n",
    "# \n",
    "# \n",
    "# \n",
    "# \n",
    "#\n",
    "class Solution:\n",
    "    def twoSum(self, nums: 'List[int]', target: 'int') -> 'List[int]':\n",
    "        length = len(nums)\n",
    "        for index,x in enumerate(nums):\n",
    "            m = target - x\n",
    "            for i in range(index+1,length):\n",
    "                if nums[i] == m:\n",
    "                    return [index,i]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoSum(self, nums: 'List[int]', target: 'int') -> 'List[int]':\n",
    "        for i in range(len(nums)):\n",
    "            for j in range(i+1,len(nums)):\n",
    "                if nums[i] + nums[j] == target:\n",
    "                    return [i,j]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from random import sample\n",
    "class Solution:\n",
    "    def twoSum(self, nums: List[int], target: int) -> List[int]:\n",
    "        for i in range(len(nums)):\n",
    "            if(target-nums[i] in nums and i != nums.index(target-nums[i])):\n",
    "                    return [i,nums.index(target-nums[i])]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoSum(self, nums: List[int], target: int):\n",
    "        n = len(nums)\n",
    "        result = []\n",
    "        for i in range(n):\n",
    "            for j in range(i+1,n):\n",
    "                if nums[i]+nums[j]==target:\n",
    "                    result.append(i)\n",
    "                    result.append(j)\n",
    "                    break\n",
    "        return result\n",
    "    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoSum(self, nums: List[int], target: int) -> List[int]:\n",
    "        hashmap={}\n",
    "        for i,num in enumerate(nums):\n",
    "            if hashmap.get(target - num) is not None:\n",
    "                return [hashmap.get(target - num),i]\n",
    "            hashmap[num] = i \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoSum(self, nums: List[int], target: int) -> List[int]:\n",
    "        for i in range(len(nums)):\n",
    "            for x in range(i+1,len(nums)):\n",
    "                if nums[i] + nums[x] == target:\n",
    "                    return i,x"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # def twoSum(self, nums: List[int], target: int) -> List[int]:\n",
    "    # \tfor i in range(len(nums)):\n",
    "    # \t\tfor j in range(i+1, len(nums)):\n",
    "    # \t\t\tif nums[i] + nums[j] == target:\n",
    "    # \t\t\t\treturn [i,j]\n",
    "    # \treturn []\n",
    "\n",
    "    \n",
    "    def twoSum(self,nums, target):\n",
    "        hashmap={}\n",
    "        for ind,num in enumerate(nums):\n",
    "            hashmap[num] = ind\n",
    "        for i,num in enumerate(nums):\n",
    "            j = hashmap.get(target - num)\n",
    "            if j is not None and i!=j:\n",
    "                return [i,j]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoSum(self, nums: List[int], target: int) -> List[int]:\n",
    "        lens = len(nums)\n",
    "        j=-1\n",
    "        for i in range(lens):\n",
    "            if (target - nums[i]) in nums:\n",
    "                if (nums.count(target - nums[i]) == 1)&(target - nums[i] == nums[i]):#如果num2=num1,且nums中只出现了一次，说明找到是num1本身。\n",
    "                    continue\n",
    "                else:\n",
    "                    j = nums.index(target - nums[i],i+1) #index(x,i+1)是从num1后的序列后找num2                \n",
    "                    break\n",
    "        if j>0:\n",
    "            return [i,j]\n",
    "        else:\n",
    "            return []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoSum(self, nums: List[int], target: int) -> List[int]:\n",
    "        n=len(nums)\n",
    "        for i in range(n):\n",
    "            for j in range(i+1,n):\n",
    "                if nums[i]+nums[j]==target:\n",
    "                    return [i,j]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoSum(self, nums: List[int], target: int) -> List[int]:\n",
    "        result = []\n",
    "        for i in range(len(nums)):\n",
    "            for j in range(i+1,len(nums)):\n",
    "                if nums[i]+nums[j]==target:\n",
    "                    result.append(i)\n",
    "                    result.append(j)\n",
    "                    break\n",
    "        return result\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoSum(self, nums: List[int], target: int) -> List[int]:\n",
    "        for i in range(len(nums)-1):\n",
    "            for j in range(i+1, len(nums)):\n",
    "                if nums[i]+nums[j] == target:\n",
    "                    return [i, j]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoSum(self, nums: List[int], target: int) -> List[int]:\n",
    "        for i in range(len(nums)):\n",
    "            for j in range(len(nums)):\n",
    "                if j == i:\n",
    "                    continue\n",
    "                else:\n",
    "                    if nums[i] + nums[j] == target:\n",
    "                        res = [i,j]\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoSum(self, nums: List[int], target: int) -> List[int]:\n",
    "        n = len(nums)\n",
    "        for i in range(n):\n",
    "            for j in range(i + 1, n):\n",
    "                if nums[i] + nums[j] == target:\n",
    "                    return [i, j]\n",
    "        \n",
    "        return []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoSum(self, nums: List[int], target: int) -> List[int]:\n",
    "        for i in range(0,len(nums)):\n",
    "            for j in range(i+1,len(nums)):\n",
    "                if nums[i]+nums[j] == target:\n",
    "                    return i,j\n",
    "                    break\n",
    "            \n",
    "        return [i,j]\n",
    "\n",
    "     \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoSum(self, nums: List[int], target: int) -> List[int]:\n",
    "        n = len(nums)\n",
    "        for i in range(n):\n",
    "            for j in range(i + 1, n):\n",
    "                if nums[i] + nums[j] == target:\n",
    "                    return [i, j]\n",
    "        \n",
    "        return []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoSum(self, nums, target) :\n",
    "        for i in range(len(nums)):\n",
    "            for j in range(i+1,len(nums)):\n",
    "                if nums[i]+nums[j]==target:\n",
    "                    return i,j\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoSum(self, nums: List[int], target: int) -> List[int]:\n",
    "        n=len(nums)\n",
    "        i=0\n",
    "        j=n-1\n",
    "        tmp=list(range(n))\n",
    "        tmp.sort(key=lambda x:nums[x])\n",
    "        while True:\n",
    "            s=nums[tmp[i]]+nums[tmp[j]]\n",
    "            if s==target:\n",
    "                return [tmp[i],tmp[j]]\n",
    "            elif s>target:\n",
    "                j-=1\n",
    "            else:i+=1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoSum(self, nums: List[int], target: int) -> List[int]:\n",
    "        for i in range(len(nums)):\n",
    "            for j in range(len(nums)):\n",
    "                if nums[i]+nums[j]==target and i!=j:\n",
    "                    return[i,j]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoSum(self, nums: List[int], target: int) -> List[int]:\n",
    "        n = len(nums)\n",
    "        for i in range(n):\n",
    "            for j in range (i+1, n):\n",
    "                if nums[i]+nums[j] == target:\n",
    "                    return [i, j]\n",
    "        return[]\n",
    "\n",
    "# 两个和的前提是至少得有两个，定义下标是最快的方法\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoSum(self, nums: List[int], target: int) -> List[int]:\n",
    "        for i in range(len(nums)):\n",
    "            for j in range(i+1, len(nums)):\n",
    "                if nums[i] + nums[j] == target:\n",
    "                    return [i, j]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoSum(self, nums: List[int], target: int) -> List[int]:\n",
    "        for i, x in enumerate(nums):  # x=nums[i]\n",
    "            for j in range(i + 1,len(nums)):  # 枚举 i 右边的 j\n",
    "                if x +nums[j]==target:\n",
    "                    return [i, j]  # \n",
    "         "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoSum(self, nums: List[int], target: int) -> List[int]:\n",
    "        list1 = nums.copy()\n",
    "        list2 = nums.copy()\n",
    "        # new_seq.sort()\n",
    "        flag = False\n",
    "        i = 0\n",
    "        for num in list1:\n",
    "            list2.remove(num)\n",
    "            find_number = target - num\n",
    "            j = 0\n",
    "            for y in list2:\n",
    "                if y==find_number:\n",
    "                    locate2 = i + j + 1\n",
    "                    flag = True\n",
    "                    break\n",
    "                j = j + 1\n",
    "            if flag:\n",
    "                break\n",
    "            i = i+1  \n",
    "        return [i, locate2]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoSum(self, nums: List[int], target: int) -> List[int]:\n",
    "        idx = {}\n",
    "        for j,x in enumerate(nums):\n",
    "            if target - x in idx:\n",
    "                return [idx[target-x],j]\n",
    "            idx[x] = j  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoSum(self, nums: List[int], target: int) -> List[int]:\n",
    "        hashtable = dict()\n",
    "        for i, num in enumerate(nums):\n",
    "            if target - num in hashtable:\n",
    "                return [hashtable[target - num], i]\n",
    "            hashtable[nums[i]] = i\n",
    "        return []"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
